import org.apache.commons.lang.StringUtils;

/**
 * @Author: Liu, Yunfeng
 * @DateTime: 2021/4/13 21:29
 * @Description: 5. 最长回文子串
 */
public class longestPalindrome {
    //暴力破解法
    public static String longestPalindrome1(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        int maxlength = 1;
        int start = 0;
        char[] array = s.toCharArray();
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (j - i + 1 > maxlength && isPalindrome(array, i, j)) {
                    maxlength = j - i + 1;
                    start = i;
                }
            }
        }
        return s.substring(start, start + maxlength);
    }

    //中心扩散法
    public static String longestPalindrome2(String s) {
        if (StringUtils.isBlank(s) || s.length() == 1) {
            return s;
        }
        int start = 0;
        int maxlength = 1;
        char[] array = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            int length1 = lengthOfPalindrome(array, i, i);
            int length2 = lengthOfPalindrome(array, i, i + 1);
            if (length1 > maxlength) {
                maxlength = length1;
                start = i - maxlength / 2;
            }
            if (length2 > maxlength) {
                maxlength = length2;//123321 mid =2,max = 6
                start = i - maxlength / 2 + 1;
            }
        }
        return s.substring(start, start + maxlength);
    }

    //动态规划。dp[i][j] = char[i] == char[j] && dp[i+1][j-1]
    public static String longestPalindrome3(String s) {
        if (StringUtils.isBlank(s) || s.length() == 1) {
            return s;
        }
        int start = 0;
        int maxlength = 1;
        int length = s.length();
        char[] arrey = s.toCharArray();
        boolean[][] dp = new boolean[length][length];
        for (int i = 0; i < length; i++) {
            dp[i][i] = true;
        }
        for (int j = 1; j < length; j++) {
            for (int i = 0; i < j; i++) {
                if (arrey[i] != arrey[j]) {
                    dp[i][j] = false;
                } else if (j - i < 3) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }

                if (dp[i][j] && maxlength < j - i + 1) {
                    start = i;
                    maxlength = j - i + 1;
                }
            }
        }
        return s.substring(start, start + maxlength);
    }

    private static boolean isPalindrome(char[] array, int start, int end) {
        if (start == end) {
            return true;
        } else {
            while (start <= end) {
                if (array[start] != array[end]) {
                    return false;
                }
                start++;
                end--;
            }
        }
        return true;
    }

    private static int lengthOfPalindrome(char[] array, int start, int end) {
        while (start >= 0 && end < array.length) {
            if (array[start] != array[end]) {
                return end - start - 1;
            }
            start--;
            end++;
        }
        return end - start - 1;
    }

    public static void main(String[] args) {
        String s = "bb";
        System.out.println(longestPalindrome1(s));
        System.out.println(longestPalindrome2(s));
        System.out.println(longestPalindrome3(s));
    }
}
